#include <aa.binary_search.h>
#include <math.h>
#include <stdio.h>

int mySqrt(int x)
{
    if (x == 0) {
        return 0;
    }
    if (x == 1 || x == 2) {
        return 1;
    }
    int lo = 0;
    // int hi = (int)sqrt(x) + 1;
    int hi = x / 2 + 1;

    for (; lo < hi;) {
        int md  = lo + (hi - lo) / 2;
        int div = x / md;
        printf("current md %d lo %d hi %d\n", md, lo, hi);
        if (div < md) {
            hi = md;
            continue;
        }
        if (div > md) {
            lo = md + 1;
            continue;
        }
        if (div == md) {
            return md;
        }
    }
    printf("no val, will return lo %d\n", lo);
    // return lo * lo > x ? lo - 1 : lo;
    return lo - 1;
}
